package com.wtgroup.demo.leetcode.org_bytedance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/29 16:37
 */
public class Q_三数之和 {

    public static void main(String[] args) {
        // int[] input = {-1, 0, 1, 2, -1, -4};
        int[] input = {-2, 0, 0, 2, 2};
        Q_三数之和 exe = new Q_三数之和();
        List<List<Integer>> res = exe.threeSum(input);
        System.out.println(res);
    }


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        if (n < 3) {
            return ans;
        }

        Arrays.sort(nums);

        for (int i = 0; i <= n - 3; i++) {
            if (i>0 && nums[i]==nums[i-1]) {
                continue;
            }
            int first = nums[i];
            int p = i+1;
            int t = n-1;
            while (p<t) {
                int tmp = first + nums[p] + nums[t];
                if(tmp>0) {
                    while(--t>p && nums[t]==nums[t+1]){}
                } else if(tmp<0) {
                    while(++p<n && nums[p]==nums[p-1]){}
                } else {
                    ans.add(Arrays.asList(first, nums[p], nums[t]));
                    while(++p<n && nums[p]==nums[p-1]){}
                    while(--t>p && nums[t]==nums[t+1]){}
                }
            }
        }

        return ans;
    }

}
